1. Field of the Invention
The present invention relates to a decoding device, a control method, and a program, and particularly, relates to a decoding device, a control method, and a program, whereby the scale of a decoding device for decoding LDPC (Low Density Parity Check) codes can be reduced for example.
2. Description of the Related Art
In recent years, study of telecommunications fields such as mobile communication or deep space telecommunication, and study of broadcasting fields such as terrestrial broadcasting or satellite digital broadcasting, for example, have been being advanced markedly, but along therewith, study relating to code theory is being actively pursued to improve the efficiency of error correction coding and decoding.
As for the theoretical limit of code capabilities, the Shannon limit provided by so-called C. E. Shannon's channel coding theorem has been known. Study relating to code theory is being performed as an object to develop codes indicating capabilities close to this Shannon limit. In recent years, as for an encoding method exhibiting capabilities close to the Shannon limit, for example, a technique so-called Turbo coding such as parallel concatenated convolutional codes (PCCC), and serially concatenated convolutional codes (SCCC) has been developed. Also, while such Turbo coding has been developed, low density parity check codes (hereafter, referred to as LDPC codes), which is an ancient known encoding method, have been being spotlighted.
LDPC codes have been proposed for the first time in “Low Density Parity Check Codes” by R. G. Gallager, Cambridge, Mass.: M. I. T. Press, 1963, and subsequently, have resulted in having been attracted in “Good error correcting codes based on very spare matrices” by D. J. C. MacKay, Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999, “Analysis of low density codes and improved designs using irregular graphs” by M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998, and so forth.
LDPC codes have been known to obtain capabilities close to the Shannon limit as the code length has been lengthened, as with Turbo codes and so forth. Also, LDPC codes have a property wherein the minimum distance is in proportion to code length, and accordingly as for the features thereof, excellent block error probability property, and further the fact that so-called error floor phenomenon, which is observed in the decoding properties of Turbo codes or the like, seldom occurs, can be cited as advantages.
Specific description will be made below regarding such LDPC codes. Note that LDPC codes are linear codes, and while it is not always necessary to be binary, description will be made assuming that LDPC codes are binary.
With LDPC codes, it is the maximum feature that a parity check matrix defining the LDPC codes thereof is a nondense matrix. Here, a nondense matrix is a matrix made up of an extremely small number of “1” of matrix components, and if we say that a nondense parity check matrix is denoted as H, as for such a parity check matrix H, for example, as illustrated in FIG. 1, the hamming weight of each row (the number of “1”) (weight) is “3”, and also the hamming weight of each line is “6”, and so on.
Thus, the LDPC codes defined by the parity check matrix H wherein the hamming weights of each line and each row are constant are referred to as regular LDPC codes. On the other hand, the LDPC codes defined by the parity check matrix H wherein the hamming weights of each line and each row are not constant are referred to as irregular LDPC codes.
Encoding using such LDPC codes is realized by generating a generator matrix G based on the parity check matrix H, and generating a codeword by multiplying a binary information message by the generator matrix G. Specifically, an encoding device for performing encoding using LDPC codes first calculates the generator matrix G wherein Expression GHT=0 holds between the transposed matrix HT of the parity check matrix H and the generator matrix G. Here, in the event that the generator matrix G is a k×n matrix, the encoding device multiplies the generator matrix G by an information message (vector u) made up of k bits to generate a codeword c (=uG) made up of n bits. The codeword generated by this encoding device is subjected to mapping such as the value of a code bit “0” being mapped as “+1”, and the value of a code bit “1” being mapped as “−1”, and is transmitted, and is consequently received at the reception side via a predetermined communication channel.
On the other hand, decoding of LDPC codes is an algorithm proposed by Gallager calling this as probabilistic decoding, and can be performed by a message passing algorithm using probability propagation (belief propagation) on a so-called Tanner graph, which is made up of variable nodes (also referred to as message nodes), and check nodes. Here, variable nodes and check nodes are also simply referred to as nodes below as appropriate.
However, with probabilistic decoding, a message exchanged between nodes is an actual value, so in order to solve this analytically, it is necessary to trace the probabilistic distribution itself of the message indicating a continuous value, resulting in requiring an analysis accompanying extreme difficulty. Therefore, Gallager has proposed an algorithm A or an algorithm B as a decoding algorithm of LDPC codes.
Decoding of an LDPC code is performed in accordance with a procedure such as illustrated in FIG. 2, for example. Now, let us say that the i'th of reception data of an LDPC code having a code length is U0 (u0i), the j'th message output from a check node (message output from the j'th branch connected to a check node) is uj, and the i'th message output from a variable node (message output from the i'th branch connected to a variable node) is vi. Also, the term “message” mentioned here is an actual value that represents the identity of a value “0” using a so-called log likelihood ratio.
First, with decoding of an LDPC code, as illustrated in FIG. 2, in step S11, the reception data U0 (u0i) is received, the message uj is initialized to “0”, and also a variable k representing an integer as a repeat processing counter is initialized to “0”, the flow proceeds to step S12. In step S12, the message vi is obtained by performing the variable node calculation shown in Expression (1) based on the reception data U0 (u0i), and further the message uj is obtained by performing the check node calculation shown in Expression (2) based on the message vi.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                          tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, the dv and dc in Expression (1) and Expression (2) are parameters that indicate the number of “1” in the vertical direction (rows) and in the lateral direction (lines) of the parity check matrix H, and are arbitrarily selectable respectively. For example, (3, 6) code yields dv=3, and dc=6.
Note that with the calculation of Expression (1) or (2), the message input from a branch (edge) to output a message is not employed as the target of an OR or AND operation, and accordingly, the range of an OR or AND operation is 1 through dv−1, or 1 through dc−1. Also, the calculation shown in Expression (2) can be performed by creating the table of the function R(v1, v2) shown in Expression (3) that is defined as 1 output as to two inputs v1 and v2 beforehand, and employing this continuously (recursively) such as shown in Expression (4).x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)  (3)uj=R(v1,R(v2,R(v3, . . . R(vdc−2, vdc−1))))  (4)
In step S12, the variable k is further incremented by “1”, and the flow proceeds to step S13. In step S13, determination is made whether or not the variable k is a predetermined number of repeated decoding times N or more. In step S13, in the event that determination is made that the variable k is less than the N, the flow returns to step S12, and thereafter, the same processing is repeatedly performed.
Also, in the event that determination is made in step S13 that the variable k is not less than the N, the flow proceeds to step S14, where the message v which is a decoding result finally output by performing the calculation shown in Expression (5) is obtained and output, and the decoding processing of the LDPC code is completed.
                    v        =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Here, the calculation of Expression (5) is performed using the message uj from all of the branches connected to a variable node, which is different from the calculation of Expression (1).
With such decoding of an LDPC code, exchange of a message between nodes is performed in the event of (3, 6) code for example, such as illustrated in FIG. 3. Note that the nodes shown with in FIG. 3 represent variable nodes, where the variable node calculation shown in Expression (1) is performed. Note that the nodes shown with “+” in FIG. 3 represent check nodes, where the check node calculation shown in Expression (2) is performed. Particularly, with the algorithm A, a message is binarized, the exclusive OR logical operation of dc−1 input messages (message vi input to a check node) is performed at the nodes shown with “+”, and in the event that dv−1 input messages (message uj input to a variable node) have all a different bit value as to reception data R at the variable nodes shown with “=”, the signs thereof are inverted and output.
Also, on the other hand, in recent years, study relating to an implementation method of decoding of LDPC codes has been performed. First, decoding of an LDPC code will be schematically described prior to description regarding the implementation method.
FIG. 4 is an example of the parity check matrix H of (3, 6) LDPC code (encoding ratio of ½, code length of 12). The parity check matrix H of an LDPC code can be written and represented with a Tanner graph such as FIG. 5. Here, in FIG. 5, the nodes represented with “+” are check nodes, and the nodes represented with “=” are variable nodes. The check nodes and variable nodes correspond to the lines and rows of the parity check matrix respectively. A crossline between a check node and a variable node is a branch (edge), and corresponds to the “1” of the parity check matrix H. That is to say, in the event that the component of the j'th line and the i'th row of the parity check matrix is 1, the i'th variable node (node of “=”) from the top, and the j'th check node (node of “+”) from the top are connected by a branch in FIG. 5. A branch represents that the bits of the LDPC code (of reception data) corresponding to a variable node have the constraint condition corresponding to a check node. Note that FIG. 5 is the Tanner graph of the parity check matrix H in FIG. 4.
A sum product algorithm serving as a decoding method of LDPC codes repeatedly performs a variable node calculation and a check node calculation.
At a variable node the variable node calculation of Expression (1) is performed such as FIG. 6. That is to say, in FIG. 6, the message vi corresponding to a branch to be calculated (the i'th branch of the branches connected to a variable node) is calculated using the messages u1 and u2 from the residual branches connected to a variable node, and the reception data u0i. The messages corresponding to other branches are also calculated in the same way.
Prior to description regarding a check node calculation, Expression (2) is rewritten such as Expression (6) using the relation of Expression a×b=exp {ln(|a|)+ln(|b|)}×sign(a)×sign(b). However, sign(x) is 1 (logical 0) when x≧0, and is −1 (logical 1) when x<0.
                                                                        u                j                            =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
Further, when defining a nonlinear function Φ(x)=−ln(tan h(x/2)) in x≧0, the inverse function Φ−1(x) thereof is represented with Expression Φ−1(x)=2 tan h−1(e−x), so Expression (6) can be written such as Expression (7).
                              u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
At a check node the check node calculation of Expression (7) is performed such as FIG. 7. That is to say, in FIG. 7, the message uj corresponding to a branch to be calculated (the j'th branch of the branches connected to a check node) is calculated using the messages v1, v2, v3, v4, and v5 from the residual branches connected to a check node. The messages corresponding to other branches are also calculated in the same way.
Note that the function Φ(x) can be also represented as Φ(x)=ln((ex+1)/(ex−1)), and with x>0, Φ(x)=Φ−1(x), i.e., the calculation result of the nonlinear Φ(x) and the calculation result of the inverse function Φ−1(x) thereof are the same. When implementing the functions Φ(x) and Φ−1(x) on hardware, implementation is sometimes made using an LUT (Look Up Table), but both share the same LUT.
Also, the variable node calculation of Expression (1) can be broken down into Expression (5) and the following Expression (8).vi=v−udv  (8)
Therefore, the calculations of Expression (5), Expression (8), and Expression (7) are repeatedly performed, whereby the variable node calculation of Expression (1) and the check node calculation of Expression (7) can be repeatedly performed. In this case, of the variable node calculations of Expression (5) and Expression (8), the calculation result of Expression (5) can be determined as the final decoding result as it is.
In the event of implementing the sum product algorithm on hardware, it is necessary to perform the variable node calculation (the calculation of a variable node) represented with Expression (1) (or Expression (5) and Expression (8)), and the check node calculation (the calculation of a check node) represented with Expression (7) repeatedly with a suitable circuit scale and operating frequency.
Description will be made regarding the implementation method of full serial decoding for performing decoding by simply sequentially performing the calculation of each of the nodes one by one as an implementation example of a decoding device.
FIG. 8 illustrates a configuration example of a decoding device for performing decoding of LDPC codes.
With the decoding device in FIG. 8, the message corresponding to one branch is calculated for each one clock of an operating clock.
Specifically, the decoding device in FIG. 8 is made up of a message calculation unit 101, message memory 104, reception data memory 105, and a control unit 106. Also, the message calculation unit 101 is made up of a variable node calculator 102 and a check node calculator 103.
With the decoding device in FIG. 8, the message calculation unit 101 sequentially reads out a message from the message memory 104 one by one, and calculates the message corresponding to a desired branch using the message thereof. Subsequently, the message obtained by the calculation thereof is stored in the message memory 104. The decoding device in FIG. 8 performs repeat decoding by repeatedly performing the above processing.
That is to say, reception data (LDPC code) D100 which is a log likelihood ratio representing the identity of code 0 (or 1) that can be obtained by receiving an LDPC code transmitted is supplied to the reception data memory 105, and the reception data memory 105 stores the reception data D100 thereof.
At the time of a variable node calculation, the reception data memory 105 reads out the stored reception data in accordance with the control signal supplied from the control unit 106, and supplies this to the variable node calculator 103 of the message calculation unit 101 as reception data D101.
Also, at the time of a variable node calculation, the message memory 104 reads out the stored message (check node message uj) D102 in accordance with the control signal supplied from the control unit 106, and supplies this to the variable node calculator 102. The variable node calculator 102 performs the variable node calculation of Expression (1) using the message D102 supplied from the message memory 104, and the reception data D101 supplied from the reception data memory 105, and supplies the message (variable node message) vi obtained as a result of the variable node calculation thereof to the message memory 104 as a message D103.
Subsequently, the message memory 104 stores the message D103 that is supplied from the variable node calculator 102 thus described above.
On the other hand, at the time of a check node calculation, the message memory 104 reads out the stored variable node message vi in accordance with the control signal supplied from the control unit 106 as a message D104, and supplies this to the check node calculator 103.
The check node calculator 103 performs the check node calculation of Expression (7) using the message D104 that is supplied from the message memory 104, and supplies the message (check node message) uj obtained by the check node calculation thereof to the message memory 104 as a message D105.
Subsequently, the message memory 104 stores the message D105 that is supplied from the check node calculator 103 thus described above.
The message D105 from the check node calculator 103 that the message memory 104 stored, i.e., the check node message uj is read out as the message D102 at the time of the next variable node calculation, and is supplied to the variable node calculator 102.
FIG. 9 illustrates a configuration example of the variable node calculator 102 in FIG. 8 for performing variable node calculations one by one.
The variable node calculator 102 includes two input ports P101 and P102 as input ports to which a message (data) is externally supplied (input), and one output port P103 as a port for supplying (outputting) a message externally. Subsequently, the variable node calculator 102 performs the variable node calculation of Expression (1) using the message that is input from each of the input ports P101 and P102, and outputs the message obtained as a result thereof from the output port P103.
That is to say, the input port P101 is supplied with the reception data D101 read out from the reception data memory 105. Also, the input port P102 is supplied with the message D102 (check node message uj) read out from the message memory 104.
The variable node calculator 102 reads in the message D102 (message uj) from the check node corresponding to each line of the parity check matrix from the input port P102 one by one, and supplies the message D102 thereof to a calculator 151 and FIFO memory 155. Also, the variable node calculator 102 reads in the reception data D101 from the reception data memory 105 from the input port P101 one by one, and supplies this to a calculator 157.
The calculator 151 integrates the message D102 by adding the message D102 (message uj) and a value D151 stored in a register 152, and restores the integration value obtained as a result thereof in the register 152. Note that in the event of the messages D102 from all of the branches across one row of the parity check matrix being integrated, the register 152 is reset to zero.
In the event that the messages D102 across one row of the parity check matrix are read in one by one, and the integration value of the messages D102 of one row worth are stored in the register 152, i.e., in the event that the integration value (Σuj of j=1 through dv) wherein the messages D102 (messages uj) from all of the branches across one row of the parity check matrix are integrated is stored in the register 152, a selector 153 selects the value stored in the register 152, i.e., the integration value D151 (Σuj of j=1 through dv) wherein the messages D102 (messages uj) of all of the branches across one row of the parity check matrix are integrated, and outputs this to a register 154 to store this.
The register 154 supplies the stored value D151 to the selector 153 and a calculator 156 as a value D152. The selector 153 selects the value D152 supplied from the register 154, and outputs this to the register 154 to restore this until immediately before the value wherein the messages D102 of one row worth are integrated is stored in the register 152. That is to say, the register 154 supplies the value previously integrated to the selector 153 and the calculator 156 until the messages D102 (messages uj) from all of the branches across one row of the parity check matrix are integrated.
On the other hand, the FIFO memory 155 delays the message D102 from a check node to supply this to the calculator 156 as a value D153 until a new value D152 (Σuj of j=1 through dv) is output from the register 154. The calculator 156 subtracts the value D153 supplied from the FIFO memory 155 from the value D152 supplied from the register 154. That is to say, the calculator 156 subtracts the message uj supplied from a desired branch from the integration value (Σuj of j=1 through dv) of the messages D102 (messages uj) of all of the branches across one row of the parity check matrix to obtain the subtraction value thereof (Σuj of j=1 through dv−1), and supplies this to the calculator 157.
The calculator 157 adds the reception data D101 from the input port P101, and the subtraction value from the calculator 156 (Σuj of j=1 through dv−1), and outputs the addition value obtained as a result thereof from the output port P103 as a message D103 (message vi).
As described above, the variable node calculator 102 performs the variable node calculation of Expression (1) (vi=u0i+Σuj), and outputs the message (variable node message) vi obtained as a result thereof from the output port P103.
FIG. 10 illustrates a configuration example of the check node calculator 103 in FIG. 8 for performing check node calculations one by one.
The check node calculator 103 includes one input port P111 as an input port to which a message (data) is externally supplied (input), and one output port P112 as a port for supplying (outputting) a message externally. Subsequently, the variable node calculator 103 performs the check node calculation of Expression (7) using the message that is input from the input port P111, and outputs the message obtained as a result thereof from the output port P112.
That is to say, the input port P111 is supplied with the message D104 (variable node message Vi) read out from the message memory 104.
With the check node calculator 103, the message D104 (message vi) from the variable node corresponding to each row of the parity check matrix is read in from the input port P111 one by one, and the lower bits except for the most significant bit thereof, i.e., the absolute value D122 (|vi|) of the message D104 is supplied to an LUT 121, and also the most significant bit, i.e., the sign bit D121 of the message D104 is supplied to an EXOR circuit 129 and FIFO (First In First Out) memory 133.
The LUT 121 is an LUT for outputting the calculation result of the nonlinear function Φ(x) in the check node calculation of Expression (7) with the value that is input thereto as an argument x, reads out the calculation result D123 (Φ(|vi|)) of the calculation of the nonlinear function Φ(|vi|) in response to supply of the absolute value D122 (|vi|), and supplies this to a calculator 122 and FIFO memory 127.
The calculator 122 integrates the calculation result D123 by adding the calculation result D123 (Φ(|vi|)) and a value D124 stored in a register 123, and restores the integration value obtained as a result thereof in the register 123. Note that in the event that the calculation result D123 (Φ(|vi|)) as to the absolute values D122 (|vi|) of the messages D104 of all of the branches across one line of the parity check matrix are integrated, the register 123 is reset to zero.
In the event that the messages D104 across one line of the parity check matrix are read in one by one, and the integration value wherein the calculation result D123 of one line worth is integrated is stored in the register 123, a selector 124 selects the value stored in the register 123, i.e., the integration value D124 (ΣΦ(|vi|) of i=1 through i=dc) wherein Φ(|vi|) obtained from the messages D104 (messages vi) from all of the branches across one line of the parity check matrix is integrated, and outputs this to a register 125 as a value D125 to store this. The register 125 supplies the stored value D125 to the selector 124 and a calculator 126 as a value D126.
The selector 124 selects the value D126 supplied from the register 125, and outputs this to the register 125 to restore this until immediately before the integration value wherein the calculation results D123 of one line worth are integrated is stored in the register 123. That is to say, the register 125 supplies the integration value of Φ(|vi|) previously integrated to the selector 124 and the calculator 126 until Φ(|vi|) obtained from the messages D104 (messages uj) from all of the branches across one line of the parity check matrix is integrated.
On the other hand, the FIFO memory 127 delays the calculation result D123 (Φ(|vi|)) that the LUT 121 outputs until a new value D126 (ΣΦ(|vi|) of i=1 through i=dc) is output from the register 125, and supplies this to the calculator 126 as a value D127. The calculator 126 subtracts the value D127 supplied from the FIFO memory 127 from the value D126 supplied from the register 125, and supplies the subtraction result thereof to an LUT 128 as a subtraction value D128. That is to say, the calculator 126 subtracts Φ(|vi|) obtained through the message supplied from a desired branch (message vi of i=dc) from the integration value (ΣΦ(|vi|) of i=1 through i=dc) of Φ(|vi|) obtained from the messages D104 (messages vi) from all of the branches across one line of the parity check matrix, and supplies the subtraction value thereof (ΣΦ(|vi|) of i=1 through i=dc−1) to the LUT 128 as a subtraction value D128.
The LUT 128 is an LUT for outputting the calculation result of the inverse function Φ−1(x) of the nonlinear function Φ(x) in the check node calculation of Expression (7) with the value that is input thereto as an argument x, outputs the calculation result D129 (Φ−1(ΣΦ(|vi|))) of the calculation of the inverse function Φ−1(ΣΦ(|vi|)) in response to supply of the subtraction value D128 (ΣΦ(|vi|) of i=1 through i=dc−1) from the calculator 126.
Note that as described above, the calculation result of the nonlinear function Φ(x) and the calculation result of the inverse function Φ−1(x) are equal, and accordingly, the LUT 121 and LUT 128 have the same configuration.
In parallel with the above processing, the EXOR circuit 129 calculates exclusive OR between the value D131 stored in a register 130 and the sign bit (bit represents positive/negative) D121, whereby multiplication is made between the sign bits D121 of the messages D104, and the multiplication result D130 is restored in the register 130. Note that in the event that the sign bits D121 of the messages D104 from all of the branches across one line of the parity check matrix are multiplied, the register 130 is reset.
In the event that the multiplication result D130 (Πsign(vi) of i=1 through i=dc) wherein the sign bits D121 of the messages D104 from all of the branches across one line of the parity check matrix are multiplied is stored in the register 130, a selector 131 selects the value stored in the register 130, i.e., the value D131 (Πsign(vi) of i=1 through i=dc) wherein the sign bits D121 of the messages D104 from all of the branches across one line of the parity check matrix are multiplied, and outputs this to a register 132 as a value D132 to store this. The register 132 supplies the stored value D132 to the selector 131 and an EXOR circuit 134 as a value D133.
The selector 131 selects the value D133 supplied from the register 132, and outputs this to the register 132 to restore this until immediately before the multiplication result D130 (Πsign(vi) of i=1 through i=dc) wherein the sign bits D121 of the messages D104 from all of the branches across one line of the parity check matrix are multiplied is restored in the register 130. That is to say, the register 132 supplies the value previously stored to the selector 131 and the EXOR circuit 134 until the sign bits D121 of the messages D104 (messages vi) from all of the branches across one line of the parity check matrix are multiplied.
On the other hand, the FIFO memory 133 delays the sign bit D121 until a new value D133 (Πsign(vi) of i=1 to i=dc) is supplied to the EXOR circuit 134, and supplies this to the EXOR circuit 134 as one bit value D134. The EXOR circuit 134 calculates exclusive OR between the value D133 supplied from the register 132 and the value D134 supplied from the FIFO memory 133, whereby the value D133 is divided by the value D134 to output the division result thereof as a division value D135. That is to say, the EXOR circuit 134 divides the multiplication value of the sign bits D121 (sign(vi)) of the messages D104 from all of the branches across one line of the parity check matrix by the sign bit D121 (sign(vi)) of the message D104 from a desired branch, and outputs the division value (Πsign(vi) of i=1 to i=dc−1) thereof as a division value D135.
Subsequently, with the check node calculator 103, a bit string wherein the calculation result D129 output from the LUT 128 is taken as lower bits, and the division value D135 output from the EXOR circuit 134 is taken as the most significant bit (sign bit) is output from the output port P112 as a message D105 (message uj).
As described above, with the check node calculator 103, the calculation of Expression (7) is performed to obtain a message (check node message) uj.
Note that though not shown in the drawing, with the decoding device in FIG. 8, the calculation of Expression (5) is performed instead of the variable node calculation of Expression (1) at the final stage of decoding, and the calculation result is output as the final decoding result.
According to the decoding device in FIG. 8, the LDPC code of various types of parity check matrix can be decoded as long as there is sufficient capacity for the message memory 104 (FIG. 8), the FIFO memory 155 of the variable node calculator 102 (FIG. 9), and the FIFO memory 127 and 133 of the check node calculator 103 (FIG. 10).
FIG. 11 is a timing chart illustrating the read/write timing of a message as to the message memory 104 of the decoding device in FIG. 8.
With the decoding device in FIG. 8, at the time of a variable node calculation, the message (check node message) uj from a check node is read out from the message memory 104, and while the variable node calculator 102 of the message calculator 101 performs a variable node calculation using the message uj read out from the message memory 104, the message (variable node message) vi obtained as a result of the variable node calculation thereof is written in the message memory 104.
Also, at the time of a check node calculation, the message (variable node message) vi from a variable node is read out from the message memory 104, and while the check node calculator 103 of the message calculator 101 performs a check node calculation using the message vi read out from the message memory 104, the message (check node message) uj obtained as a result of the check node calculation thereof is written in the message memory 104.
Accordingly, with the decoding device in FIG. 8, it is necessary to perform readout of a message from the message memory 104, and writing of the message obtained as a result of a variable node calculation or a check node calculation (hereafter, simply referred to as node calculation by integrating both) using the message thereof simultaneously event at the time of a variable node calculation or a check node calculation.
Therefore, the message memory 104 is made up of, for example, one RAM (Random Access Memory) #A serving as one memory bank, and another RAM#B serving as another memory bank. Access to each of the RAM#A and RAM#B enables two apparent accesses as to the message memory 104 simultaneously.
The timing chart in FIG. 11 represents the read/write timing as to the RAM#A and RAM#B making up the message memory 104.
In FIG. 11, first of all, the message necessary for obtaining the message corresponding to the branch of a certain check node or variable node (hereafter, simply referred to as node by integrating both as appropriate) node#1 is read out from the RAM#A (R(node#1)), and a node calculation is performed using the message thereof. Subsequently, the message corresponding to the branch of the node node#1 obtained as a result of the node calculation thereof is written in the RAM#A (W(node#1)), and at the same time, the message necessary for obtaining the message corresponding to the branch of the next node node#2 is read out from the RAM#B (R(node#2)), and a node calculation is performed.
Further, the message corresponding to the branch of the node node#2 obtained as a result of the node calculation thereof is written in the RAM#B (W(node#2)), and at the same time, the message necessary for obtaining the message corresponding to the branch of the next node node#3 is read out from the RAM#A (R(node#3)), and a node calculation is performed. Hereinafter, in the same way, read/write of the message corresponding to each of the RAM#A and RAM#B making up the message memory 104 is continuously performed.
Note that with the decoding device in FIG. 8, in the event of decoding an LDPC code using repeat decoding for alternately performing a check node calculation and a variable node calculation, one time decoding (one set of a check node calculation and a variable node calculation) requires the number of clocks twice as many as the number of messages, resulting in requiring high-speed operations.
Therefore, with regard to the LDPC code of a particular parity check matrix, a decoding device wherein messages are obtained simultaneously regarding p nodes by providing the multiple, p message calculation units 101, and one time decoding can be performed with the number of clocks of 1/p in the case of the decoding device in FIG. 8, i.e., a decoding device which can operate with not so high operating frequency has been proposed (see Japanese Unexamined Patent Application Publication No. 2004-364233, for example).